\documentclass[a4paper,12pt]{report}
\usepackage[utf8x]{inputenc}
\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc}
\usepackage{setspace}
\usepackage{indentfirst}
% Title Page
\title{Algumas considerações em \textit{token} ring}
\author{Adroaldo}


\begin{document}
\maketitle

\begin{abstract}
\end{abstract}

\onehalfspace


\section{Hipóteses}
\begin{itemize}
 \item Cada nó tem um único identificador.
 \item Conexão vai ser em função de sinal
 \item Um \underline{varal} é utilizado para encaminhamento de dados.
 \item Um \textit{token} somente falha se cair junto com o sucessor. I.e., se o \textit{token}
passado caiu é porque o nó que deveria ter recebido este \textit{token} caiu.

\end{itemize}

\section{Estórias}
\subsection{Procedimento de entrada- antigo. O novo foi comentado}

Um nó X faz \textit{broadcast} solicitando entrada em anel. Para cada nó Y em anel
que escutar (o \textit{broadcast}), espera receber \textit{token}, então envia uma mensagem
ao nó X contendo seu ID e ID do sucessor dele. 

%Depois, o nó Y fica monitorando um
%\emph{Ack} do antigo sucessor dele para o X. Esse \emph{Ack} é uma resposta a mensagem
%``Atribuir predecessor'' do X para o antigo sucessor do Y.

Se o X consegue escutar o Y e o sucessor de Y, então o nó Y inicia o procedimento de
entrada do nó X no anel. E, o X envia ``atribuir predecessor'' com o seu ID ao sucessor de Y.

Se o nó X não consegue escutar ou Y ou sucessor de Y então, o nó Y passa a vez para
o seu sucessor tentar o procedimento de entrada para X. Se nenhum nó Y no anel consegue
introduzir o nó X no anel, então este último vai aguardar por algum tempo $\alpha$ antes
de executar o procedimento de entrada novamente.

Na figura \ref{fig:innode} apresentamos um exemplo de procedimento de entrada.
Inicialmente, o nó R faz \textit{broadcast} solicitando a entrada. O nó D escuta
\textit{broadcast}, então espera receber o \textit{\textit{token}}, daí envia o seu ID e ID
do sucessor dele (L) ao nó R. Este último envia uma mensagem ``Atribuir predecessor'' ao
L, e depois D envia ``Atribuir predecessor'' ao R.

\vspace{.1in}
\underline{\textbf{Observação:}} Caso o nó X não receba \emph{Ack} do antigo sucessor
de Y. O nó Y verificará se o antigo sucessor dele falhou: Se sim, ele busca na sua
tabela de conectividade (na ordem de transmissão de \textit{token}) um nó para fechar o anel,
e o procedimento de entrada de X é refeito à partir do Y; Se não falhou, o Y passará
a vez para o seu sucessor tentar o procedimento de entrada para X.


\subsection{Procedimento de saída}
\subsubsection{Nó comum}

Primeiro, o nó cessante espera receber o \textit{token}. Quando o \textit{token} estiver no seu poder,
envia ao seu predecessor o pacote \textit{set successor} com identificador do seu sucessor. Se o predecessor
escuta o sucessor, então predecessor tenta conectar ao sucessor enviando \textit{set predecessor}. Se não escuta o sucessor,
então busca na sua tabela de conectividade um nó e envia para este nó o pacote \textit{set predecessor}.


\subsubsection{Nó proprietário}

O nó cessante espera receber o \textit{token} em varal. Então, envia pacote ao seu predecessor e sucessor (seus vizinhos) em varal
avisando que vai sair. Estes vizinhos esperam receber a mensagem do nó cessante, então 
enviam um \textit{broadcast} cada com intuíto de alcançar nós em anel do nó cessante. Os nós (em anel do nó cessante)
que escutarem ambos \textit{broadcast} participarão em eleições para escolher um novo proprietário. Após eleito
o novo proprietário receberá identificador de cada nó em anel. Uma vez que o novo proprietário possui os identificadores
de predecessor e sucessor em varal, ele enviará os \textit{token}s \textit{set successor} e \textit{set predecessor}
para o seu predecessor e sucessor em varal, respectivamente. No anel do proprietário cessante, se ninguém escutar 
ambos \textit{broadcast}, o anel será isolado de varal. E, consequentemente, o procedimento de saída de
\textbf{Nó comum} será aplicado tanto em anel isolado quanto em varal.


\subsubsection{Nó proprietário de varal}


O nó espera receber o \textit{token} em varal, daí convoca eleições (enviando \textit{broadcast}) em varal. Todos os nós
que escutaram a convocação partecipam das eleições para encontrar um novo proprietário. Uma vez encontrado um novo
proprietário, ele enviará um ``\textit{solicit role}'' para o proprietário cessante solicitando as informações de 
privilégio de proprietário. Também, o novo proprietário muda o \textit{varal address} para o seu identificador. Por 
enquanto, o nó cessante é um \underline{nó proprietário} do seu anel. Para encontrar outro proprietário do anel:
quando o predecessor e o sucessor em varal, de proprietário cessante, escutarem a convocação
de eleições, esperam receber o \textit{token} e enviam um \textit{broadcast} cada. E o mesmo procedimento para saída de
\underline{nó proprietário} será aplicado. 


\subsection{Falhas}
\begin{flushleft}
O \textit{token} é monitorado através de \textbf{Ack implicito - AckI}.
Quando um nó envia um \textit{token}, ele terá a confirmação de entrega que o seu envio foi bem sucedido - AckI, quando
ele escutar uma transmissão de \textit{token} (com endereço de anel igual a endereço de anel no nó em causa)
original em seu sucessor.\\

\end{flushleft}

\subsubsection{Nó comum}
\begin{flushleft}
Um nó é considerado em falha, se o predecessor dele não receber um AckI após
um determinado número de tentativas de transmissões de \textit{token}. 
\end{flushleft}

\subsubsection{Nó proprietário}
Um nó proprietário incrementa o Gen\_Seq a cada rodada do \textit{token}. Se algum nó, exceto o proprietário,
recebe um \textit{token} com o Gen\_Seq igual ao seu Gen\_Seq, então este nó assume que
o proprietário está em falha.

\subsection{Recuperação a falha}
\begin{flushleft}
 O nosso protocolo implementa mecanismos para recuperar as falhas
causadas por quedas inesperadas de nós em \textit{token} ring. À seguir, descrevemos
as estratégias adotadas:
  \begin{itemize}
   \item Se o predecessor de um nó simples identificar a falha do nó. Este predecessor
  busca na sua tabela de conectividade (em ordem de transmissão de \textit{token}) um nó para
  fechar o anel. Essa busca deve ser feita de modo que o anel seja reconstruído reduzindo
  menor número de nós possível.
   \item a queda inesperada de um coordenador causará rutura em varal e em anel. Neste
  caso, teremos dois componentes isolados: predecessor em varal do coordenador em
  falha busca um nó viável para fechar o varal (usando as estratégias explicadas no item
  anterior);(assim, permitirá que o anel perdido junte ao varal); também, o predecessor no
  anel cujo coordenador falhou busca um nó na sua tabela de conectividade
  para fechar o anel (usando as estratégias explicadas no item anterior). Uma vez que o anel
  foi reconstruído este predecessor inicia as eleições para encontrar um novo proprietário.
  Em seguida, este proprietário vai candidatar (com prioridade) para voltar ao varal.
  \end{itemize}

\end{flushleft}

\subsection{Considerações: Varal}
\begin{itemize}
 \item 
\end{itemize}


\subsection{Considerações: anel}
\begin{itemize}
 \item Se a saída do proprietário do anel for planejada, uma eleição é feita para encontrar um
 novo proprietário.
 \item Um nó x que entra em algum anel, a excessão do varal, só pode aderir ao varal
se for eleito(após alguma eleição) após o proprietário do anel perder a conexão com o varal ou após o dono do
anel sair.
\end{itemize}

\subsection{Transmissão de dados}
\begin{flushleft}
 Se o nó destino estiver ao alcance do nó origem, então a transmissão é feita diretamente. Senão
os dados passam de sucessor a sucessor até chegar ao nó destino. 
\end{flushleft}
\subsubsection{Transmissão de dados inter-anel}
\begin{flushleft}
 Caso o nó destino pertença a um outro anel,
os dados são enviados ao proprietário do anel (que contém nó origem) e o procedimento de transmissão de dados acima
é aplicado ao varal.
\end{flushleft}

\subsection{Ack de dados}
\begin{flushleft}
 Quando o nó destino recebe os dados, ele envia um \underline{Ack} (sem esperar pelo \textit{token}) avisando
o recebimento. Consequentemente, os encaminhadores podem remover os mesmos dados da fila.
\end{flushleft}

\subsection{Ack de \textit{token}}
\begin{flushleft}
 
\end{flushleft}

\subsection{Atualização de tabela de IDs em anel}
 As tabelas de IDs devem ser replicadas a todos os nós de anel.
\begin{flushleft}

\end{flushleft}



  
\section{Perguntas}
\begin{itemize}
 \item Quando se deve construir um novo anel ?
 \item Como os nós vão se descobrir ?
 \item O campo sucessor deve existir no \textit{token} ?
 \item Qual o tamanho o varal deve ter, qual a relação com os aneis ? Resposta: Uma variável configurável
em tempo tcl ou então fixo no código(para saber o número de nós máximo em varal. Varal é o anel inicial.)
 \item A emissão de dado é \textit{broadcast} ou \textit{unicast} ?
\end{itemize}

\section{\textit{Token}s e as descrições}

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
FC & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\end{tabular}
\caption{Formato de \textit{Token}} 
\end{table}


\subsection{Tipos de Quadros}
\begin{enumerate}

\item \textit{Token} Normal\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00000001 & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\end{tabular}\\

Provê exclusividade ao uso de canal de comunicação em anel.

\item \textit{Token} de eleição\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline
00000010 & RA & DA & SA & MAX\_POWER & n\_Ch\\
\hline
\end{tabular}\\

Passa de nó em nó. Permite eleger um novo proprietário de anel.

\item Meta-\textit{Token} de proprietário eleito\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00000011 & RA & DA & SA & ELECTED & Data\\
\hline
\end{tabular}\\

Passa de nó em nó anunciando o novo proprietário e coletando IDs de nós no referido anel.

\item \textit{Token} de Solicitar sucessor\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00000100 & RA & Br. & SA & NoN\\
\hline
\end{tabular}\\

Faz-se \textit{Broadcast} deste \textit{token} para solicitar sucessor em varal.

\item \textit{Token} de atribuição de predecessor\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00000101 & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\end{tabular}\\

Usado em aderência de um novo nó e no procedimento de saída.

\item \textit{Token} de atribuição de sucessor\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00000110 & RA & DA & SA & NS\\
\hline
\end{tabular}\\

Usado em aderência de um novo nó e no procedimento de saída. O campo NS
contém informações de futuro sucessor em anel.

\item Pacote de dados\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline
00000111 & P & RA & DA & SA & Data\\
\hline
\end{tabular}\\

Representa pacote de dados com prioridade P.

\item Pacote de Ack de dados

\item \textit{Token} Deletado\\
Para evitar que um \textit{token} (em varal ou anel) seja recuperado, o valor 00000000 é atribuido ao campo FC de um \textit{token}.

\item \textit{Token} de varal\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00001001 & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\end{tabular}\\

Provê exclusividade ao uso de canal de comunicação em varal.

\item \textit{Token} de eleição em varal\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline
00001010 & RA & DA & SA & MAX\_ID & Num\_Ch\\
\hline
\end{tabular}\\

Passa de nó em nó. Permite eleger um novo proprietário de varal.

\item Meta-\textit{Token} de proprietário eleito em varal\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00001011 & RA & DA & SA & ELECTED & Data\\
\hline
\end{tabular}\\

Passa de nó em nó anunciando um novo proprietário e coletando IDs de nós em varal.

\item \textit{Token} de Solicitar sucessor em varal\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00001100 & RA & Br. & SA & NoN\\
\hline
\end{tabular}\\

Faz-se \textit{Broadcast} deste \textit{token} para solicitar sucessor em varal.

\item \textit{Token} de atribuição de predecessor em varal\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00001101 & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\end{tabular}\\

Usado em aderência de um novo nó e no procedimento de saída.

\item \textit{Token} de atribuição de sucessor em varal\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00001110 & RA & DA & SA & NS\\
\hline
\end{tabular}\\

Usado em aderência de um novo nó e no procedimento de saída. O campo NS
contém informações de futuro sucessor em varal.

\item Pacote de dados em varal\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline
00001111 & P & RA & DA & SA & Data\\
\hline
\end{tabular}\\

Representa pacote de dados em varal com prioridade P.


\item \textit{Token} de apresentação de nó\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00010000 & RA & Br. & SA\\
\hline
\end{tabular}\\

Um nó faz \textit{broadcast} deste \textit{token} quando deseja
adverter serviços a alguns nós.

\item \textit{Token} aviso de aderência
\begin{tabular}{|c|c|c|c|c|}
\hline
00010001 & RA & DA & SA & ID\\
\hline
\end{tabular}\\

Este \textit{token} é utilizado para avisar que o nó N acabou de entrar no anel cujo endereço é RA. Ele transita de 
sucessor em sucessor até o predecessor do nó ID.

\item \textit{Token} aviso de saída
\begin{tabular}{|c|c|c|c|c|}
\hline
00010010 & RA & DA & SA & ID\\
\hline
\end{tabular}\\

Este \textit{token} é utilizado para avisar que o nó N saiu do anel cujo endereço é RA. Ele transita de 
sucessor em sucessor até o predecessor do nó ID.

\item \textit{Token} de reapresentação
\begin{tabular}{|c|c|c|c|c|}
\hline
00010011 & RA & DA & SA & ID\\
\hline
\end{tabular}\\

Este \textit{token} é utilizado quando um nó quer enviar ID dele para o sucessor. Sempre que
houver saída ou queda inesperada em um anel, este \textit{token} é enviado e recebido entre os 
nós restantes no anel.

\end{enumerate}

\section{Gubi notes}
O pedaço de anel que fica por fora pode ser alertado que está fora, através do eminente sucessor do detetor de saida.
Adicionar um \textit{token} que vai monitar as solicitações de entrada.

formação de varal : O proprietário de anel é aquele q tiver o maior sinal com o varal.
A tabela de nós em anel deve ser distribuida a todos os nós.
Nomenclatura hieráquica entre os aneis.

\section{Estados de um nó}
\begin{itemize}
 \item \textbf{Tem \textit{token}:} estado em que um nó está com \textit{token}
 \item \textbf{Está no varal:} quando um nó faz parte de varal
 \item \textbf{Estacionário:} estado em que um nó está em algum anel, mas sem \textit{token}
 \item \textbf{desocupado:} estado em que um nó está visível, porém fora de qualquer anel
 \item \textbf{monitoramento:} estado em que um nó escuta transmissões de \textit{token} do seu sucessor
 \item Um nó entra em estado \textbf{solicitante} para solicitar a conexão de um nó da sua tabela de conectividade
\end{itemize}

\end{document}